00100	CS126                                     March 9, 1970
00200	
00300	                       NOTES ON LISP NOTATION
00400	
00500	1.S-expressions
00600		1.1 Atoms A, A3, PLUS, etc.
00700		1.2 Compound S-expressions  (A.B), (A.(B.C)), etc.
00800		1.3 List notation  (A B C), ((A B) A C), etc.
00900	
01000	2. Basic operators - car[x], cdr[x], cons[x,y], atom[x], eq[x,y]
01100		Examples car[((A.B).C)] = (A.B)
01200			cdr[((A.B).C)] = C
01300			cons[(A.B) , C] = ((A.B).C)
01400			atom[A] = T, atom[(A.B)] = F
01500			eq[A,B] = F, eq[A,(A.B)] = F, eq[(A.B),(A.C)] = F
01600			eq[A,A] = T, eq[(A.B),(A.B)] has value  T  if the
01700	two copies of (A.B) are represented by the same pointer in memory.
01800	
01900	3.In list notation we have
02000			car[(A B C D)] = A
02100			cdr[(A B C D)] = (B C D)
02200			cons[A,(B C D)] = (A B C D)
02300	All this is a consequence of the fact that (A B C D) can be regarded
02400	as merely an abbreviation for  (A.(B.(C.(D.NIL)))).
02500	
02600	4. Abbreviations
02700		ax  for  car[x]  so that  a(A B C) = A
02800		dx  for  cdr[x]  so that  d(A B C) = (B C)
02900		x.y  for  cons[x,y]  so that  A.(B C D) = (A B C D) {Although
03000	this notation is convenient it tempts the inexperienced to confuse
03100	the cons operation with the  .  of the dot notation.}
03200		adaax  for  car[cdr[car[car[x]]]], etc. which can also
03300	be written  cadaar[x]  constituting a lesser abbreviation.
03400		nx  for  eq[x,NIL], {also written  null[x]}.
03500		(x y ... z)  for  cons[x,cons[y,...cons[z,NIL]...]] {This
03600	is the operation that forms lists from the elements.  It is also
03700	denoted by  list[x,y,...,z].  The ... is intended to indicate
03800	that the operation can take an arbitrary number of arguments.}
03900		atx  for  atom[x]
04000		x eq y  for eq[x,y]
04100		x=y  for  equal[x,y]
04200		x∧y  for  if x then y else F
04300		x∨y  for  if x then T else y
04400		¬x  for  if x then F else T
04500	
04600	5. Examples of simple LISP programs.
04700		5.1 Alternate elements of a list.
04800	alt[x] = if nx ∨ ndx then x else [ax].alt[ddx]
04900	Thus  alt[(A B C D E)] = (A C E)
05000		5.2 Substitution of  x  for  y  in  z.
05100	subst[x,y,z] = if atz then [if z eq y then x else z]
05200		else subst[x,y,az].subst[x,y,dz]
05300	Thus  subst[(TIMES X Y),X,(PLUS X Y)] = (PLUS (TIMES X Y) Y)
05400		5.3 Membership of an atom in a list of atoms.
05500	member[x,u] = ¬nu∧[x eq au ∨ member[x,du]]
05600	Thus  member[A,(A B C)] =T  and  member[A,(B C D)] = F.
05700		5.4 Inclusion of one list in another.
05800	included[u,v] = nu ∨ [member[au,v] ∧ included[du,v]]
05900	Thus  included[(A B C),(D C B A)] = T.
06000		5.5 The union of two lists.
06100	union[u,v] = if nu then v else if member[au,v] then union[du,v]
06200	else [au].union[du,v]